#pragma once

namespace solution_086
{

struct ListNode
{
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) { }
    ListNode(int x) : val(x), next(nullptr) { }
    ListNode(int x, ListNode* next) : val(x), next(next) { }
};

class Solution
{
public:
    ListNode* partition(ListNode* head, int x)
    {
        if (head == nullptr)
            return head;

        ListNode root;
        root.next = head;

        auto prev = head->val < x ? head : &root;
        for (auto node = prev; node->next; ) {
            auto next = node->next;
            if (next->val < x) {
                node->next = next->next;

                next->next = prev->next;
                prev->next = next;
                prev = prev->next;
            }
            node = next;
        }

        return root.next;
    }
};

}  /* namespace solution_086 */
